This application includes a computer program listing appendix contained on a compact disc, in file listing.txt, created on May 25, 2001, and having a size of 20,775 bytes, the contents of which are hereby incorporated by reference.
This invention generally relates to graphics data processing, and relates more specifically to mechanisms for storing, dynamically reconstructing, and navigating a three-dimensional virtual world using a database system.
Computers can generate graphical displays that show an object or scene in three apparent physical dimensions. Such three-dimensional (3D) graphics or images are extremely useful for visualizing real-world objects, scenes, or processes. Systems and software processes for generating 3D graphics are described in detail in W. Newman et al., xe2x80x9cPrinciples of Interactive Computer Graphicsxe2x80x9d (New York: McGraw-Hill, Inc., 1979).
When polygons, surfaces, and other 3D graphical elements are combined into a computer-generated scene that resembles a real environment, the scene is called a xe2x80x9cvirtual worldxe2x80x9d and the computer is said to display xe2x80x9cvirtual realityxe2x80x9d. Computer programs are available for defining, editing, and displaying virtual worlds using a personal computer or a graphics workstation.
Recently, a global packet-switched network known as the Internet has attracted wide use. A local computer can connect to a distant server, request a file or an image from the server, and receive the requested information immediately. The Internet operates according to several standard protocols. Packets of data are communicated among Internet host computers (xe2x80x9cserversxe2x80x9d) using the Transmission Control Protocol (TCP) and Internet Protocol. The name and location of each server connected to the Internet is indexed at several computers known as Domain Name Servers (DNSs). A local computer can look up the name of a remote server using a DNS, connect to the remote computer, and send and receive information.
One popular technology enjoying wide use with the Internet is known as the World Wide Web. The World Wide Web enables a computer to locate a remote server using the DNS and then establish a connection to the server and retrieve information using a communication protocol called the Hypertext Transfer Protocol (HTTP). A Uniform Resource Locator (URL) uniquely identifies each page of information stored on the remote server. A URL is a form of network address that identifies the location of information stored in a network. The local computer requests information by providing a request containing a URL of the desired information to the remote server. The server receives the request, locates the page of information corresponding to the URL, and returns the page to the local computer over the HTTP connection. The pages of information are files prepared in the Hypertext Markup Language (HTML). The local computer runs a browser program that can read HTML files, interpret HTML codes in the files, and generate a complex graphical display.
The Virtual Reality Modeling Language (VRML) provides a way to integrate virtual reality technology with World Wide Web technology. VRML is the industry-standard description language for storing and delivering 3D information over the Internet. Using VRML, virtual worlds can be defined in human-readable text form and in a device-independent manner. The virtual world is defined in a text file that is interpreted at runtime, like a scripting language. A complete definition of the VRML language can be found in documents of the VRML organization stored at http://www.vrml.org/, and in other published sources.
Using VRML, a virtual world is defined in a written language in terms of nodes and fields. Nodes are abstractions of real-world objects and concepts. Examples include spheres, lights, and material descriptions. Nodes contain fields and events. Messages may be sent between nodes along routes. Nodes are organized into a representation of a virtual world called a scene graph. A field is a property or attribute of a node. Each type of node has a fixed set of fields. Fields may contain data and one or many values.
In the past, virtual worlds have been stored in a graphical format, such as a bitmap, a set of inter-related sprites, vectors, or other complex numeric information. The text format of virtual worlds defined using VRML uses significantly less storage space than a graphical representation of a virtual world. However, the tradeoff for having less storage is that computation must be performed to transform the VRML text file into an image. As a result, a 3D scene is not rendered and displayed as quickly as it would be if the scene were stored in a graphical representation. As available computing power continues to increase, the processing required to render an image at runtime becomes less significant.
Generally, a VRML virtual world is defined and described in a text file using the VRML language. The browser is provided with a VRML interpreter, generally in the form of a program which can xe2x80x9cplug-inxe2x80x9d to the browser. An example of a VRML interpreter is the Cosmo browser plug-in available from Silicon Graphics, Inc. VRML worlds are stored on a server. The term xe2x80x9cVRML worldxe2x80x9d or xe2x80x9cworldxe2x80x9d in this context refers both to textual source code and the display resulting from interpretation of the source code by a computer using the VRML interpreter. The browser requests a VRML world by providing its URL to the server. For example, the URL of a VRML world is included in a Web page of a Web site, or associated (as by hyper-linking) with a portion of the Web page. When a user selects or clicks on the hyperlink, the browser sends the URL to the server. The server locates the selected VRML world and returns it in text file format to the local computer. The browser reads the VRML world, interprets the VRML commands, opens a browser window or frame on the computer display, and generates a graphic display. Thus, the server generates the virtual world and the browser renders the world. In this way, virtual worlds can be displayed in a window of a browser.
For example, the following VRML source code will generate a virtual world comprising a red cone when it is run in a VRML-enabled browser:
This example defines a VRML world that has one xe2x80x9cnodexe2x80x9d called xe2x80x9cShapexe2x80x9d. The source code of the world defines the xe2x80x9cShapexe2x80x9d node as having a particular appearance, apparent material, color, and geometry.
A key advantage of VRML is that the application programmer who writes the VRML world need not write platform-specific code; the same VRML world will run on a personal computer with an Intel(copyright) processor, a workstation that has a SPARC(copyright) processor, an Apple(copyright) Macintosh(copyright) computer, or a graphics workstation, provided that a VRML-enabled browser is running.
In general, a VRML world is prepared by writing a text file containing VRML commands, in human-readable source code form, using a general-purpose text editor or a VRML editor such as Silicon Graphics"" CosmoSuite or IDS"" VRealmsBuilder. A complicated world having numerous shapes or textures may require thousands of lines of VRML code. In the past, such complex VRML worlds have been stored in the form of a single sequential-record text file. To display the world, a VRML-enabled browser loads the entire world as a unit, and then interprets the entire world starting from the top of the source file and proceeding to the bottom. The VRML interpreter then determines what portion of the world is visible from the current point of view xe2x80x9cseenxe2x80x9d by the browser, and displays that portion of the world.
However, this approach is slow and inefficient. The display screen of the user""s computer generally shows only a portion of a world. Accordingly, in a complex world only a small portion of the world may be visible on the display at a particular time. The remainder of the world may lie conceptually behind the viewer, to the side, or beyond a vanishing point on the horizon. In such cases, it is inefficient and unnecessary for the browser to load, interpret, and attempt to display invisible portions of the world.
This approach also imposes significant burdens on systems that comprise display stations or xe2x80x9cclientsxe2x80x9d coupled over a network to a server that contains the VRML file. It is inefficient and burdensome on the network to transfer a large VRML file as a complete unit over the network to a display station, when only a portion of the world is within the field of view of the display station.
The conventional approach also may be impractical in a system comprising a server that stores the VRML file and a remotely located display terminal that lacks a large storage device. For example, computing environments are being developed using servers and remotely connected network computers. The network computers have limited memory and lack large storage devices such as disk drives. A large VRML file may exceed the memory storage space available in a network computer, so that the VRML world cannot be displayed.
Another disadvantage of the conventional approach is that the VRML file is monolithic and static. A complicated world defined in a large VRML file is difficult to maintain and update. For example, to make a small change to a world, such as removing a tree from a scene, it would be necessary to: retrieve the entire VRML file; find the portion of the file in which the tree is defined; update the file using a text editor to remove the tree; and save the updated file as a single unit. In addition, the same process of editing, saving, and reloading must be used when the user wishes to add new elements to the world. Manipulating a VRML file in this manner excessively burdens the user and the computing system, and is slow and error-prone.
Database systems are computer programs optimized for creating, storing, manipulating, and reporting on information stored in tables. The tables are organized as an array of rows and columns. The values in a row are associated with each other in some way; for example, a row may store a complete data record relating to a sales transaction, a person, or a project. Columns of the table define discrete portions of the rows that have the same general data format. For example, columns define fields of the records.
Database systems provide a powerful way to organize large amounts of information and retrieve selected information. They operate rapidly and can be applied to real-time data-entry situations in which data is constantly entered, retrieved, and updated. However, in the past, adapting databases to particular applications has been slow and cumbersome, requiring custom code. In addition, database systems generally have limited report-generating capabilities especially with respect to delivering information over the Web. Most data is displayed in tabular reports, or other line-oriented and column-oriented methods. While some database systems provide graphic display capabilities, the displays are usually limited to simple graphs and charts.
In addition, in most database systems, graphs and charts cannot be prepared using rapidly changing data from a database that forms a part of a real-time application. Usually, to generate a graph the user must specify a range of data in a table, and invoke a graph generating utility. While the graph is displayed, changes may occur in the data, but the changes are not reflected in the graph in real time. This limits the usefulness of the graphical display features.
Based on the foregoing, there is a clear need for a system, process and product that provides rapid and efficient creation, modification and updating of a virtual world.
There is also a need for a system, process and product that enables elements of a virtual world to be located rapidly and modified efficiently.
There is a need for a system, process and product that incrementally displays only that portion of a virtual world that is visible to a user or browser, or within their field of view, at a particular time.
There is a need for a system, process and product that displays a virtual world efficiently and effectively on a remote display device that has limited local storage space.
There is a need for a system or process that allows elements or information to be inserted dynamically into a virtual world while the world is displayed.
There is also a need for a system or process that permits elements of a graphical world to be modified in real time based upon a changing source of data.
There is also a need for a system or process that permits such modification based upon information retrieved in real time from a table of a database management system.
The foregoing needs, and other needs that will become apparent in the following description, are fulfilled by embodiments of the invention, which comprises, in one aspect, a method of generating a display of a virtual world from a first source definition of the virtual world, the method comprising the steps of reading a description of each of a plurality of nodes that are in the virtual world; decomposing the description of each of the plurality of nodes and storing values identified from the description in a database; recomposing a second source definition of the virtual world using the values in the database; and delivering the second source definition to a display client that is configured to display the virtual world using the second source definition.
One feature of this aspect is that the step of decomposing the description further comprises the steps of storing the values for each of the nodes in one table of the database. Another feature is that the step of recomposing further comprises the step of retrieving the description of each of the nodes from the table. Still another feature involves the steps of inserting in the second source definition a reference to a data value for each of the nodes.
According to another feature, the step of storing a description further comprises the step of storing, in a node table of the database, an identifier of the node, an identifier of a parent node to which the node is related subordinately, and an order value defining an order of the node in relation to a second node subordinately related to the parent node. Another feature involves storing a plurality of fields in the first source definition, each of the fields being associated with one of the nodes; and for each of the fields, storing a field identifier, a field value, and a node identifier in a field table of the database.
Yet another feature involves the steps of storing in the first source definition a reference to an external source definition of a second virtual world; and inserting in the second source definition a second description of the second virtual world composed from the external source definition. A related feature is that the composing step includes the steps of receiving a world identifier of the first source definition; selecting all nodes of the first source definition from the node table based on the world identifier and using a selection function of the database; and writing the nodes to the second source definition according to a grammar of a virtual world definition language.
Another feature is that the step of detecting includes the step of parsing the virtual world to identify the nodes. Still another feature is that the parsing step comprises the step of parsing the first source definition of the virtual world according to a grammar of a Virtual Reality Modeling Language (VRML). A related feature is that the composing step includes the steps of receiving a world identifier of the virtual world; selecting all nodes of the virtual world from the node table based on the world identifier and using a selection function of the database; and writing the nodes to a VRML file according to the grammar. According to another feature, the method further comprises the steps of displaying an outline view of the nodes; receiving an identification of a selected node to be modified and a modification value; locating the selected node in the table; and updating the selected node with the modification value. Yet another feature is that the method further comprises the steps of storing a plurality of fields in the first source definition, each of the fields being associated with one of the nodes; establishing in the database a plurality of field tables, each of the field tables corresponding to a field type defined in a Virtual Reality Modeling Language; and for each of the fields, storing a field identifier, a field value, and a node identifier in one of the field tables that corresponds to the field. The invention also encompasses other aspects. Additional objects, advantages and novel features of the invention will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following or may be learned by practice of the invention. The objects and advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.